\ifx\wholebook\relax \else

\documentclass[b5paper, punct=kaiming]{ctexart}

\usepackage[cn]{../../prelude}

\setcounter{page}{1}

\begin{document}

\title{前言}

\author{刘新宇
\thanks{{\bfseries 刘新宇} \newline
  \url{https://github.com/liuxinyu95} \newline}
  }

\maketitle
\fi

\markboth{前言}{}

\chapter*{第二版前言}
\phantomsection  % so hyperref creates bookmarks
\addcontentsline{toc}{chapter}{第二版前言}

很多人的工作在身后才得以出版，如费马、伽罗瓦、吴敬梓、曹雪芹……很多人不肯发表不完美的工作，即使在后人看来已经很优秀、很重要了，如高斯；很多人的一些工作甚至毁于天灾人祸，遗失了，如黎曼。我们应该感谢萨缪尔·费马（整理了父亲散落的手稿和页边笔记）、刘维尔（发掘整理了伽罗瓦的遗稿）、戴德金（抢救了黎曼部分被焚毁的笔记），以及那些佚名资助、整理、出版这些作品的人。我们应该感谢那些不计经济盈亏，坚持保存、传播人类知识的出版社。今天，科技和互联网的进步大大改善了工作、记录、整理、出版的漫长过程，我得以锱铢积累地从2009年开始把一些习作、心得、发现用中英文分享到互联网上的版本控制系统中。到2015年，这些内容大致汇集成一本关于基本函数式算法和数据结构的初稿，并在2017年出版，名为《算法新解》。

对比前人，这真是太幸运了。我的工作远远比不上他们哪怕一丝的光辉，而且还有众多国内外优秀同行的作品尚未出版、引进给读者呢。我只有怀着感恩的心情，感谢编辑的信任，感谢所有读者的匆匆一瞥和容忍，然后听取、收集大家的意见，尽最大的努力修改、订正。我从2020年底开始重写此书，到2023年5月完成。这一版的主要变化有：

\begin{enumerate}
\item 重写了所有章节，尽量用符号和形式化的表达替换掉繁冗的叙述。
\item 调整了内容结构。(a) 将列表提前为第一章，方便不熟悉函数式编程的读者入门；(b) 增加了B-树的列表对实现。在附录中增加了红黑树和AVL树的命令式删除算法；(c) 去掉了后缀树一章，在命令式字符串匹配部分，集中介绍最具代表性的KMP算法，去掉了Boyer-Moore匹配算法；(d) 增加了全部120道习题的答案。
\item 根据第一版读者反馈，统一了例子程序语言。函数式用Haskell作为例子，命令式用虚拟语言Bourbaki（布尔巴基是20世纪一群顶级数学家组成的学派的笔名，包括安德烈·韦伊、亨利·嘉当等。虚拟人物尼古拉·布尔巴基被称为最伟大却并不存在的数学家，暗示Bourbaki语言不存在，但却能从中看到一些熟悉的影子，如Python、Java、C等）。并尽量把例子程序置于各章后的附录。
\item 修正了一些错误。
\end{enumerate}

冈崎（Chris Okasaki）和伯德（Richard Bird）的优秀工作奠定了基本函数式数据结构和算法的主要内容。得益于此，本书可以说是对他们所建框架的剪裁与组织。尽管函数式编程的应用和前沿技术发展日新月异，基本算法部分却相对稳定。这使得我可以用十多年时间逐渐修改、完善，并把本书\footnote{本书电子版可以在github上获得，如果希望获得纸质版，请在github上联系我。}呈现到读者面前。

\vspace{15mm}

\rightline{二零二三年十月于北京}


\chapter*{第一版前言}
\phantomsection  % so hyperref creates bookmarks
\addcontentsline{toc}{chapter}{第一版前言}

尽管我们在课堂上学习基本算法，但除了编程竞赛、求职面试，在实际工作中很少用到它们。很多算法和数据结构已经在程序库中实现好了，我们只需要了解如何使用。谈到人工智能和机器学习算法时，实际上说的是数学模型而非基本算法和数据结构。基本算法在解决一些“有趣”的问题时，会扮演关键角色。让我们看看下面两个例子。

\section*{最小可用数}
\label{min-free} \index{最小可用数}

理查德$\cdot$伯德提出过一个问题：找出不在一个列表中出现的最小数字（\cite{fp-pearls}第一章）。我们经常用数字标识实体，如身份证号、银行账户、电话号码等。我们希望找到一个最小的没有被占用数字。假设都是自然数，所有正在使用的数字记录在一个列表中：

\begin{Verbatim}[fontsize=\footnotesize]
[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
\end{Verbatim}

不在这个列表中的最小自然数是10。这个题目看上去是如此简单，我们可以立即写出下面的解法：

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $x \gets 0$
  \Loop
    \If{$x \notin A$}
      \State \Return $x$
    \Else
      \State $x \gets x + 1$
    \EndIf
  \EndLoop
\EndFunction
\end{algorithmic}

其中符号$\notin$的实现如下：

\begin{algorithmic}[1]
\Function{`$\notin$'}{$x, X$}
  \For{$i \gets 1 $ to $|X|$}
    \If{$x = X[i]$}
      \State \Return False
    \EndIf
  \EndFor
  \State \Return True
\EndFunction
\end{algorithmic}

其中$|X| = n$表示序列$X$的长度。有些编程语言内置了这一线性查找的实现。当列表包含几百万个数字时，这个方法的的性能很快变差。它消耗的时间和$n$的平方成正比。在一台双核2.10GHz处理器，2G内存的计算机上，其C语言实现需要5.4秒才能在十万个数字中找到答案。当数量上升到一百万时，则需要8分钟。

\subsection*{改进}
对$n$个自然数$x_1, x_2, \dotsc , x_n$，如果存在小于$n$的可用数，必然存在某个$x_i$不在区间$[0, n)$\footnote{左开右闭区间$[a, b)$包括$a$但不包括$b$。}内。否则这些数一定是$0, 1, \dotsc, n - 1$的某个排列，这种情况下，最小的可用自然数是$n$。

\be
\textit{minfree}(x_1, x_2, \dotsc, x_n) \leq n
\label{eq:min-free}
\ee

我们用一个长度为$n + 1$的数组$F$，来标记区间$[0, n]$内的某个整数是否可用。

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $F \gets$ [False, False, $\dotsc$, False] \Comment{$n+1$个}
  \For{$x$ in $A$}
    \If{$x < n$}
      \State $F[x] \gets$ True
    \EndIf
  \EndFor
  \For{$i \gets 0$ to $n$}
    \If{$F[i] =$ False}
      \State \Return $i$
    \EndIf
  \EndFor
\EndFunction
\end{algorithmic}

$F$中的元素都初始化为假。遍历$A$中的数字，如果$x < n$，就将标志$F[x]$置为真。最后再扫描$F$，找到第一个值为假的位置。算法用时和$n$成正比。我们使用了$n + 1$个而不是$n$个标志，用以处理$sort(A) = [0, 1, 2, \dotsc, n-1]$的情况。这个方法需要$O(n)$的空间来存储标志$F$。查找结束后，$F$又被释放了。反复的申请和释放也会消耗时间。我们可以预先准备好足够长的数组，每次查找复用。另外可以使用二进制位保存标志节约空间。在相同的计算机上，相应的C语言程序仅用0.023秒就可以处理一百万个数字。

\subsection*{分而治之}
分而治之的策略将问题分解为若干规模较小的子问题，然后逐步解决以得到最终的结果。将所有满足$x_i \leq \lfloor n/2 \rfloor$的自然数放入子序列$A'$；其它放入子序列$A''$。根据\cref{eq:min-free}，如果序列$A'$的长度正好是$\lfloor n/2 \rfloor$，说明前一半$A'$已经“满了”，答案一定在$A''$中，否则答案在$A'$中。通过这一划分，问题的规模减小了。在子序列$A''$中递归查找时，边界情况发生了变化。查找下界从0变成了$\lfloor n/2 \rfloor + 1$。我们将定义修改为$search(A, l, u)$，其中$l$是下界，$u$是上界。起始时：$\textit{minfree}(A) = search(A, l = 0, u = |A|-1)$。

\begin{lalign*}
  search(\nil, l, u) & = l \\
  search(A, l, u) & = \begin{cases}
    |A'| = m - l + 1 : & search(A'', m+1, u) \\
    \text{否则} : & search(A',  l, m)
  \end{cases}
\end{lalign*}

其中：

\[
\begin{cases}
m = \lfloor \dfrac{l + u}{2} \rfloor \\
A' = [x \leq m, x \in A], A'' = [x > m, x \in A]
\end{cases}
\]

这一方法不需要额外空间\footnote{递归需要$O(\lg n)$的栈空间，但可以通过尾递归优化消除。}。每次需要$O(|A|)$次比较划分$A'$和$A''$，使问题规模减半。算法用时为$T(n) = T(n/2) + O(n)$，通过主定理得到结果$O(n)$\footnote{我们也可以这样分析：第一次需要$O(n)$次比较划分，第二次需要比较$O(n/2)$次，第三次需要比较$O(n/4)$次……总时间为$O(n + n/2 + n/4 + \dotsc) = O(2n) = O(n)$。}。下面的例子代码实现了这一算法。

\lstset{frame = single}
\begin{Haskell}
minFree xs = bsearch xs 0 (length xs - 1)

bsearch xs l u | xs == [] = l
               | length as == m - l + 1 = bsearch bs (m + 1) u
               | otherwise = bsearch as l m
    where
      m = (l + u) `div` 2
      as = [x | x <- xs, x <= m]
      bs = [x | x <- xs, x > m]
\end{Haskell}

递归的深度和调用栈都是$O(\lg n)$。我们可以消除递归用迭代实现：

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $l \gets 0, u \gets |A|$
  \While{$u - l > 0$}
    \State $m \gets \lfloor \dfrac{u + l}{2} \rfloor$
    \State $\textit{left} \gets l$
    \For{$right \gets l$ to $u - 1$}
      \If{$A[right] \leq m$}
        \State 交换 $A[\textit{left}] \leftrightarrow A[right]$
        \State $\textit{left} \gets \textit{left} + 1$
      \EndIf
    \EndFor
    \If{$left < m + 1$}
      \State $u \gets \textit{left}$
    \Else
      \State $l \gets \textit{left}$
    \EndIf
  \EndWhile
\EndFunction
\end{algorithmic}

如\cref{fig:divide}所示，这段程序对数组中的元素进行划分。$left$之前的元素都不大于$m$，而$left$和$right$之间的元素都大于$m$。

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.7]{img/partition-by}  % by pdfcrop
  \caption{数组划分。位于$0 \leq i < left$的元素满足$A[i] \leq m$，位于$left \leq i < right$的元素满足$A[i] > m$，剩余的元素尚未处理。}
  \label{fig:divide}
\end{figure}

\section*{正规数}

第二道趣题是如何寻找第1500个正规数。正规数是只含有2、3、5这三种因子的自然数\footnote{在数论中叫作5-光滑数。在计算机科学中又叫作哈明数以纪念理查德$\cdot$哈明。}。2、3、5本身也是正规数。$60 = 2^23^15^1$是第25个正规数。数字$21 = 2^03^17^1$含有因子7，所以不是正规数。定义$1=2^03^05^0$是第0个正规数。前10个正规数如下：

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

\subsection*{穷举法}
我们可以从1开始，逐一检查所有自然数，对每个数把2、3、5这些因子不断去掉，检查最终结果是否为1：

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $x \gets 1$
  \While{$n > 0$}
    \State $x \gets x + 1$
    \If{\Call{Valid?}{$x$}}
      \State $n \gets n - 1$
    \EndIf
  \EndWhile
  \State \Return $x$
\EndFunction
\Statex
\Function{Valid?}{$x$}
  \While{$x \bmod 2 = 0$}
    \State $x \gets x / 2$
  \EndWhile
  \While{$x \bmod 3 = 0$}
    \State $x \gets x / 3$
  \EndWhile
  \While{$x \bmod 5 = 0$}
    \State $x \gets x / 5$
  \EndWhile
  \State \Return $x = 1$ ?
\EndFunction
\end{algorithmic}

随着$n$增大，穷举法用时迅速增加。在同样的计算机上，其C语言实现需要40.39秒才找到第1500个正规数（860934420）。

\subsection*{构造性解法}
取模和除法是耗时的计算\cite{Bentley}。如果不再检查每一个数的因子，而是从2、3、5构造正规数，这样问题就转换为如何从小到大依次产生正规数序列。我们可以使用队列，从一侧加入，另一侧取出元素。先放入的先被取出，称为先进先出FIFO（First In First Out）。把第0个正规数1加入队列，不断取出正规数，分别乘以2、3、5，产生3个正规数并按大小顺序加入队列。丢弃重复的数，如\cref{fig:queues}所示。

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.5]{img/regular-num-1q}
  \caption{前4步}
  \label{fig:queues}
\end{figure}

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $Q \gets [1]$
  \While{$n > 0$}
    \State $x \gets$ \Call{Dequeue}{$Q$}
    \State \Call{Unique-Enqueue}{$Q, 2x$}
    \State \Call{Unique-Enqueue}{$Q, 3x$}
    \State \Call{Unique-Enqueue}{$Q, 5x$}
    \State $n \gets n-1$
  \EndWhile
  \State \Return $x$
\EndFunction
\Statex
\Function{Unique-Enqueue}{$Q, x$}
  \State $i \gets 0, m \gets |Q|$
  \While{$i < m$ 且 $Q[i] < x$}
    \State $i \gets i + 1$
  \EndWhile
  \If{$i \geq m$ 或 $x \neq Q[i]$}
    \State \Call{Insert}{$Q, i, x$}
  \EndIf
\EndFunction
\end{algorithmic}

对于长度为$m$的队列，\textproc{Unique-Enqueue}需要$O(m)$时间按序、无重复地插入新元素。队列的长度随着$n$线性增加（每取出一个后最多插入三个新元素，增加的比率$\leq 2$），总运行时间为$O(1 + 2 + 3 + \dotsb + n) = O(n^2)$。\Cref{fig:big-O-1q}显示了队列的访问次数和$n$之间的关系，形状为二次曲线，反映出$O(n^2)$的复杂度。

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.5]{img/big-O-1q}
  \caption{队列访问次数和$n$的关系}
  \label{fig:big-O-1q}
\end{figure}

在同样的计算机上，其C语言实现仅用0.016秒就输出了答案，比穷举法快2500倍。我们也可以用递归实现，令$xs$为包含所有正规数的无穷序列$[x_1, x_2, x_3, \dotsc]$。对每个正规数，将其乘以2得到的仍然是无穷正规数列：$[2x_1, 2x_2, 2x_3, \dotsc]$。同样依次乘以3、5会得到另外两个无穷正规数列。如果将这3个无穷数列合并，去除重复并将1添加到开头，就又得到了$xs$：

\be
  xs = 1 : [2x | x \gets xs] \cup [3x | x \gets xs] \cup [5x | x \gets xs]
\ee

其中$x \cons xs$表示将元素$x$连接到列表$xs$的前面，在Lisp中这个操作称为cons。1是第0个正规数，在最前面。$\cup$合并两个列表。

\[
(a \cons as) \cup (b \cons bs) = \begin{cases}
  a < b: & a : as \cup (b \cons bs) \\
  a = b: & a : as \cup bs \\
  a > b: & b : (a \cons as) \cup bs \\
\end{cases}
\]

由于(:)运算的优先级低于$\cup$，我们省略了很多括弧，例如：$a : (as \cup (b \cons bs))$可以简化为$a : as \cup (b \cons bs)$。下面是例子程序

\begin{Haskell}
xs = 1 : [2*x | x <- xs] `merge` [3*x | x <- xs] `merge` [5*x | x <- xs]

merge (a:as) (b:bs) | a < b = a : merge as (b:bs)
                    | a == b = a : merge as bs
                    | otherwise = b : merge (a:as) bs
\end{Haskell}

这一例子程序：\inlineHaskell{xs !! 1500}，在同样的计算机上用0.03秒内得到第1500个正规数。

\subsection*{队列}
上面的解法需要排除掉重复元素、扫描队列以保持有序。把所有正规数分成三个类：$Q_2 = \{2^i | i > 0\}$仅包含被2整除的数；$Q_{23} = \{ 2^i3^j | i \geq 0, j > 0 \}$、$Q_{235} = \{ 2^i3^j5^k | i,j \geq 0, k > 0\}$。其中$Q_{23}$要求$j \neq 0$，$Q_{235}$要求$k \neq 0$，保证了三类数间没有重复。每类数都用一个队列来产生。初始化$Q_2=\{ 2 \}$，$Q_{23} = \{ 3 \}$和$Q_{235} = \{ 5 \}$。每次取出三个队列头部的最小元素$x$，然后进行下面的检查：

\begin{enumerate}[(a)]
\item 如果$x$来自$Q_2$，将$2x$加入$Q_2$，$3x$加入$Q_{23}$，$5x$加入$Q_{235}$；
\item 如果$x$来自$Q_{23}$，将$3x$加入$Q_{23}$，$5x$加入$Q_{235}$。我们不应将$2x$加入$Q_2$，因为$Q_2$中不包含被3整除的数。
\item 如果$x$来自$Q_{235}$，将$5x$加入$Q_{235}$。我们不应将$2x$加入$Q_2$，$3x$加入$Q_{23}$，因为它们不包含被5整除的数。
\end{enumerate}

不断从三个队列中取出最小的$n$个元素。\cref{fig:q235}给出了前4步。

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.5]{img/q235}
  \caption{使用三个队列$Q_2$、$Q_{23}$、$Q_{235}$构造正规数的前4步。}
  \label{fig:q235}
\end{figure}

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $x \gets 1$
  \State $Q_2 \gets \{ 2 \}$, $Q_{23} \gets \{ 3 \}$, $Q_{235} \gets \{ 5 \}$
  \While{$n > 0$}
    \State $x \gets min$(\Call{Head}{$Q_2$}, \Call{Head}{$Q_{23}$}, \Call{Head}{$Q_{235}$})
    \If{$x =$ \Call{Head}{$Q_2$}}
      \State \Call{Dequeue}{$Q_2$}
      \State \Call{Enqueue}{$Q_2, 2x$}
      \State \Call{Enqueue}{$Q_{23}, 3x$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \ElsIf{$x=$ \Call{Head}{$Q_{23}$}}
      \State \Call{Dequeue}{$Q_{23}$}
      \State \Call{Enqueue}{$Q_{23}, 3x$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \Else
      \State \Call{Dequeue}{$Q_{235}$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \EndIf
    \State $n \gets n - 1$
  \EndWhile
  \State \Return $x$
\EndFunction
\end{algorithmic}

算法循环$n$次。每次从三个队列中取出最小元素，这一步需要常数时间。接着根据取出元素所在的队列，产生一到三个新数加入队列，这一步也是常数时间。整个算法复杂度为$O(n)$。

\section*{小结}
尽管两道趣题都能用穷举法解决，但随着规模增加，我们不得不寻求更好的解法。本书\textbf{不是}一本算法竞赛或面试的“刷题手册”。本书介绍常见的基本算法和数据结构，对比给出纯函数式和命令式实现，展示函数式算法和数据结构的特有思路。主要参考了冈崎的著作\cite{okasaki-book}和经典的算法教材\cite{CLRS}。本书尽量避免依赖于特定的编程语言。一方面读者会有自己的偏好，另一方面编程语言也在不断变化。我们主要使用伪代码和数学记法对算法进行定义，并附以一些例子代码。函数式的示例类似Haskell，命令式的示例是几种语言的混合体。

\begin{Exercise}[label={ex:preface}]
\Question{最小可用数趣题中，所有数都是非负整数。我们可以利用正负号来标记一个数字是否存在。首先扫描一遍列表，若$|x| < n$，其中$n$为列表长度，将位置$|x|$上的数字置为负数。之后再扫描一遍列表，找到第一个正数所在的位置就是答案。编程实现这一算法。}

\Question{$n$个数字1, 2, ..., $n$，经过某一处理后，它们的顺序被打乱了，并且某一个数$x$被改成了$y$。假设$1 \leq y \leq n$，设计一个方法能够在线性时间、常数空间内找出$x$和$y$。}

\Question{下面是一段求正规数的代码。它是一种队列解法么？
\begin{lstlisting}[language = Bourbaki]
Int regularNum(Int m) {
    [Int] nums(m + 1)
    Int n = 0, i = 0, j = 0, k = 0
    nums[0] = 1
    Int x2 = 2 * nums[i]
    Int x3 = 3 * nums[j]
    Int x5 = 5 * nums[k]
    while n < m {
        n = n + 1
        nums[n] = min(x2, x3, x5)
        if x2 == nums[n] {
            i = i + 1
            x2 = 2 * nums[i]
        }
        if x3 == nums[n] {
            j = j + 1
            x3 = 3 * nums[j]
        }
        if x5 == nums[n] {
            k = k + 1
            x5 = 5 * nums[k]
        }
    }
    return nums[m]
}
\end{lstlisting}
}
\end{Exercise}

\begin{Answer}[ref={ex:preface}]
\Question{最小可用数趣题中，所有数都是非负整数。我们可以利用正负号来标记一个数字是否存在。首先扫描一遍列表，若$|x| < n$，其中$n$为列表长度，将位置$|x|$上的数字置为负数。之后再扫描一遍列表，找到第一个正数所在的位置就是答案。编程实现这一算法。

\vspace{3mm}
\begin{Bourbaki}
Int minFree([Int] nums) {
    var n = length(nums)
    for Int i = 0 to n - 1 {
        var k = abs(nums[i])
        if k < n then nums[k] = -abs(nums[k])
    }
    for Int i = 0 to n - 1 {
        if nums[i] > 0 then return i
    }
    return n
}
\end{Bourbaki}
}

\Question{$n$个数字1, 2, ..., $n$，经过某一处理后，它们的顺序被打乱了，并且某一个数$x$被改成了$y$。假设$1 \leq y \leq n$，设计一个方法能够在线性时间、常数空间内找出$x$和$y$。

\vspace{3mm}
例如$X$ = [3, 1, 3, 5, 4]中，丢失的是$x = 2$，重复的是$y = 3$。我们给出4种解法：（1）分治、（2）鸽笼排序、（3）符号编码、（4）解方程。

\textbf{分治}方法。使用中点$m = \lfloor \dfrac{1 + n}{2} \rfloor$划分序列为两部分，左侧：$as = [a \leq m, a \gets X]$、右侧：$bs = [b > m, b \gets X]$。如果左侧长度$|as| < m$，可知丢失的数字在左侧，记$s = 1 + 2 + \dotsb + m = \dfrac{m (m + 1)}{2}$，则$x = s - sum(as)$。同时可计算出重复的数字在右侧，记$s' = (m + 1) + (m + 2) + \dotsb + n = \dfrac{(n + m + 1)(n - m)}{2}$，则$y = sum(bs) - s'$；若左侧的长度$|as| > m$，可知重复的数字在左侧。使用同样的方法，可以算出丢失的数字$x = s' - sum(bs)$，重复的数字$y = sum(as) - s$；否则，如果左侧的长度$|as| = m$，说明有$m$个不大于$m$的数字，但我们不知道它们是否是1, 2, ..., $m$的某个排列。为此，我们可以计算并比较$sum(as)$和$s$。如果相等，说明左侧没有问题，可以丢弃左侧的所有数字，然后递归地在右侧寻找$x$和$y$；否则，我们丢弃右侧，在左侧递归寻找答案。在递归查找时，需要用序列的下限$l$替换上述步骤中的1。由于每次去掉一半的列表，根据主定理，总时间复杂度为$O(n)$。

\begin{Haskell}
missDup xs = solve xs 1 (length xs) where
  solve xs@(_:_:_) l u | k < m - l + 1 = (sl - sl', sr' - sr)
                       | k > m - l + 1 = (sr - sr', sl' - sl)
                       | sl == sl' = solve bs (m + 1) u
                       | otherwise = solve as l m
      where
        m = (l + u) `div` 2
        (as, bs) = partition (<=m) xs
        k = length as
        sl = (l + m) * (m - l + 1) `div` 2
        sr = (m + 1 + u) * (u - m) `div` 2
        (sl', sr') = (sum as, sum bs)
\end{Haskell}

\textbf{鸽笼排序}。由于所有的数字都在1到$n$之间，我们可以使用鸽笼排序来重新排列数字。我们自左向右扫描，对于每个位置$i$上的数字$x$，如果$x \neq i$，我们就将它和位置$x$上的数字$y$交换。如果$x = y$，我们就找到了重复的数字，同时，我们得知丢失的数字就是$i$，重复这一交换过程，直到$x$等于$i$或者找到重复的数字。由于每个数字仅被交换一次以到达正确的位置，因此总时间复杂度为$O(n)$。

\begin{Bourbaki}
(Int, Int) missDup([Int] xs) {
    Int miss = -1, dup = -1
    for Int i = 0 to length(xs) - 1 {
        while xs[i] != i {
            Int j = xs[i]
            if xs[j] == xs[i] {
                dup = xs[j]
                miss = i
                break
            } else {
                j = xs[i]
                (xs[i], xs[j]) = (xs[j], xs[i])
            }
        }
    }
    return (miss, dup)
}
\end{Bourbaki}

\textbf{符号编码}。假设存在一个长度为$n$的标记数组，对于序列中的每个数字$x$，我们都将标记数组中的第$x$个位置做上标记。当我们遇到重复元素时，我们会发现这个位置上的标记已经做过了。记重复的数字为$d$，我们知道$s = 1 + 2 + \dotsb + n = \dfrac{n (n + 1)}{2}$，以及序列中所有的数字和$s'$。我们可以计算出丢失的数字$m = d + s - s'$。 但是这一方法需要额外长度为$n$的空间用作标记数组。由于数字的存在与否是一种二值化的信息（有、无），我们可以将其编码为数字的正负号，从而复用待查找的数字序列。对于序列中的每个数字$x$，我们将序列中第$|x|$位置上的元素标记为负数，其中$|x|$表示绝对值。如果发现某一位置已经为负了，我们就找到了重复的元素，接下来我们就可以计算出丢失的数字。

\begin{Bourbaki}
(Int, Int) missDup([Int] xs) {
    Int miss = -1, dup = -1
    Int n = length(xs)
    Int s = sum(xs)
    for i = 0 to n - 1 {
        Int j = abs(xs[i]) - 1
        if xs[j] < 0 {
            dup = j
            miss = dup + n * (n + 1) / 2 - s
            break
        }
        xs[j] = -abs(xs[j])
    }
    return (miss, dup)
}
\end{Bourbaki}

\textbf{解方程}。考虑一个简化的问题：给定一个从1到$n$的列表，去掉一个元素，然后打乱序列的顺序，怎样能够快速找出去掉的元素呢？我们可以将列表中所有的元素相加，然后从$\frac{n (n + 1)}{2}$减去这一结果就得出了答案。这一思路可以表示为如下方程：

\[
m = s - s'
\]

其中$m$表示丢失的数字，$s$是从1到$n$的累加和，$s'$是列表中所有元素的和。但是同时存在丢失的元素和重复的元素，无法仅用一个方程求出两个未知数。

\be
\sum (x[i] - i) = d - m
\label{eq:miss-dup-1}
\ee

其中左侧是列表中第$i$个元素减去$i$后的累加和。能否找出第二个独立的方程呢？思路是使用平方。如果我们将第$i$个元素的平方减去$i$的平方，然后将结果累加起来。就可以得到下面的结果：

\be
\sum (x[i]^2 - i^2) = d^2 - m^2 = (d + m)(d - m)
\label{eq:miss-dup-2}
\ee

由于$d - m$不等于0，我们可以用\cref{eq:miss-dup-1}除以\cref{eq:miss-dup-2}两侧，得到另一个方程：

\be
\sum (x[i]^2 - i^2) / \sum (x[i] - i) = d + m
\label{eq:miss-dup-3}
\ee

比较\cref{eq:miss-dup-1}和\cref{eq:miss-dup-3}，两个方程、两个未知数，这样就可以得到结果：

\[
\begin{dcases}
m = \dfrac{1}{2} (\dfrac{\sum (x[i]^2 - i^2)}{\sum (x[i] - i)} - \sum (x[i] - i)) \\
d = \dfrac{1}{2} (\dfrac{\sum (x[i]^2 - i^2)}{\sum (x[i] - i)} + \sum (x[i] - i)) \\
\end{dcases}
\]

\begin{Haskell}
missDup xs = ((b `div` a - a) `div` 2, (b `div` a + a) `div` 2) where
  ys = zip xs [1..]
  a = sum [x - y | (x, y) <- ys]
  b = sum [x^2 - y^2 | (x, y) <- ys]
\end{Haskell}
}

\Question{是的，它是一种等价的队列解法。}
\end{Answer}

\ifx\wholebook\relax \else
\section*{参考答案}
\shipoutAnswer

\begin{thebibliography}{99}

\bibitem{fp-pearls}
Richard Bird. ``Pearls of functional algorithm design''. Cambridge University Press; 1 edition (November 1, 2010). ISBN-10: 0521513383. pp1 - pp6.

\bibitem{Bentley}
Jon Bentley. ``Programming Pearls(2nd Edition)''. Addison-Wesley Professional; 2 edition (October 7, 1999). ISBN-13: 978-0201657883 （中文版：《编程珠玑》）

\bibitem{okasaki-book}
Chris Okasaki. ``Purely Functional Data Structures''. Cambridge university press, (July 1, 1999), ISBN-13: 978-0521663502

\bibitem{CLRS}
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. ``Introduction to Algorithms, Second Edition''. The MIT Press, 2001. ISBN: 0262032937. （中文版：《算法导论》）

\end{thebibliography}

\expandafter\enddocument
\fi
